Portable computing devices, for example Portable Navigation Devices (PNDs) that include GPS (Global Positioning System) signal reception and processing functionality are well known and are widely employed as in-car or other vehicle navigation systems.
The utility of such PNDs is manifested primarily in their ability to determine a route between a first location (usually a start or current location) and a second location (usually a destination). These locations can be input by a user of the device, by any of a wide variety of different methods, for example by postcode, street name and house number, previously stored “well known” destinations (such as famous locations, municipal locations (such as sports grounds or swimming baths) or other points of interest), and favourite or recently visited destinations.
The PND determines the route based upon stored geographical data, usually in the form of a digital map. The stored geographical data can include data concerning a wide variety of features, for example the position and characteristics of roads or other thoroughfares, the position and characteristics of points of interest, and the position and characteristics of geographical features, for example rivers, coastlines, or mountains.
The accuracy of the stored geographical data can vary, and the location and characteristics of features can change over time.
In operation, most PNDs periodically log their own position as a function of time, for example every five seconds. PNDs can also log other, associated, data such as speed or direction of travel as a function of time. In some cases, the PNDs also log user input data, for example relating to the position or other properties of a point of interest. The data logged by PNDs or other portable computing devices, can be referred to as probe data. Data from a single device, either a single point or a series of points obtained over time, can be referred to as a probe trace. It is known to obtain probe data from a large number of PNDs or other portable computing devices, and to process the probe data in order to verify or supplement existing geographical data, for example existing digital maps. In a simple example, if many probe traces are obtained from positions parallel to a segment of road stored in a digital map, and no or few probe traces are obtained from the stored segment of road, then it may be concluded that the position of the segment of road stored in the digital map is incorrect and should be modified.
However, the reliability of any particular set of probe data can be difficult to determine. Usually, in the case of uncoordinated events such as probe trace position capture or for reported information such as point of interest (POI) data, the accuracy and veracity of an event is highly correlated to the number of similar events recorded by independent sources. In most such cases, additional information such as direction of travel, type or name of POI, type of request, must also be considered. That is, it may be desired to know that a large number of probe traces agreed on both relative position and relative direction. Similarly it may be desired to know that POI requests came in for the same type of establishment, or were named similarly, or were uniformly “add” requests, as opposed to “delete” requests.
A particularly complex application has been in building information from uncoordinated probe traces. The trace data is relatively noisy and unreliable—some traces can diverge from their true positions by hundreds of meters without indicating a problem. Even when the error is smaller, say tens of meters, a trace may match incorrectly to a nearby road segment that is parallel to its actual location. It may be desirable to recognize such traces, and either avoid or correct them for use in determining road position, average height, speed, or other attributes at a location. Conversely, it may be desirable to build high trust for trace paths that are well corroborated by population averages—these trace paths indicate equipment that is in good repair, functioning at optimal fidelity. The value of any probe-derived data can be significantly improved by selectively weighting and using the best trace sources.
It is known to perform probe trace correlation using spatial clustering techniques. Many means of mathematical clustering are available. According to the prior art, all probe trace points can be connected by straight or curved lines, and those lines placed into a geographic index, and that index reorganized into spatial clusters. These clusters can be analyzed to determine proximity and corroboration.
The clusters are used to select portions of raw probe data that are of relevance to a particular location or feature (for example a particular segment of road) and the selected probe data is then processed to obtain further information concerning the feature or to verify digital map data concerning the feature.
Clustering by its nature collects and organizes data, and this aspect of the technique can lose or distort important information. For example, a given cluster may be considered to be a selection of trace segments. As the clustering requires a selection, nearby segments that don't meet the clustering criteria are not considered. Alternatively, clusters may be designed to overlap, meaning that one trace segment is in more than one cluster; however, such designs multiply the amount of analysis work and computation that must be done, and do not address the fundamental issue that a cluster does not completely capture the proximity relationships of the data.
Clustering falls prey to a second issue: the cluster itself must be assigned to a location representative of its members. It may be assigned to a single point or a bounding box; but in either case it is a static representation of a group of members, rather than a statistical representation around a locus—thus it suffers spatial inaccuracy.
The issues mentioned in the preceding two paragraphs can be referred to as data generalization, caused by the binary inclusion or exclusion of data from any cluster; and spatial contamination, the influence of disparate paths or errant data that are aggregated together due to spatial coincidence within a cluster's region. These issues can be only partially mitigated by techniques such as creating clusters with more overlapping content, or creating finer clustering grids. Such mitigation techniques tend to produce excessive computational burdens, with little improvement in results.
Clustering techniques can be used for trace capture points themselves (that is, without connecting them with lines or curves). Such a technique tends to fall even further from the ideal, failing to recognize common travel in sparse situations in which the points themselves are far apart, even though the traveled paths have commonality.
Known techniques for dealing with POI updates also present difficulties. Updates are usually resolved manually—by human review of each request, or using rudimentary clustering techniques to identify hot spots—again presenting issues stemming from data generalization and spatial contamination.